home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / basic.bak < prev    next >
Encoding:
Text File  |  1992-06-09  |  18.5 KB  |  716 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  basic.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef BASICH
  17. #define BASICH
  18.  
  19. #include <stream.h>
  20. #include <stdlib.h>
  21.  
  22. #ifndef __TURBOC__
  23.  
  24. #include <generic.h>
  25. #include <values.h>
  26.  
  27. #else
  28.  
  29. // TC values.h:
  30.  
  31. #define MAXINT          0x7FFF
  32. #define MAXLONG         0x7FFFFFFFL
  33. #define MAXFLOAT        3.37E+38
  34. #define MAXDOUBLE       1.797693E+308
  35.  
  36. // generic.h:
  37.  
  38. #define name2(z, y)             __name2(z, y)
  39. #define __name2(z, y)           z##y
  40. #define name3(z, y, x)          __name3(z, y, x)
  41. #define __name3(z, y, x)        z##y##x
  42. #define name4(z, y, x, w)       __name4(z, y, x, w)
  43. #define __name4(z, y, x, w)     z##y##x##w
  44.  
  45. #define declare(z, y) name2(z, declare)(y)
  46. #define implement(z, y) name2(z, implement)(y)
  47. #define declare2(z, y, x) name2(z, declare2)(y, x)
  48. #define implement2(z, y, x) name2(z, implement2)(y, x)
  49.  
  50. #endif   /* __TURBOC__ */
  51.  
  52.  
  53. //------------------------------------------------------------------------------
  54. // Global Type Definitions
  55. //------------------------------------------------------------------------------
  56.  
  57. typedef void* ent;
  58.  
  59.  
  60. typedef ent*  ent_ptr;
  61.  
  62. typedef int  (*CMP_ENT)(ent&,ent&);
  63. typedef ent  (*ENT_TO_ENT)(ent&);
  64. typedef int  (*ENT_TO_INT)(ent&);
  65. typedef void (*ENT_TO_VOID)(ent&);
  66.  
  67. typedef int  (*ANY_TO_INT)(...);
  68. typedef ent  (*ANY_TO_ENT)(...);
  69. typedef void (*ANY_TO_VOID)(...);
  70.  
  71.  
  72.  
  73.  
  74.  
  75. //------------------------------------------------------------------------------
  76. // Macros
  77. //------------------------------------------------------------------------------
  78.  
  79. #define Infinity MAXINT
  80.  
  81. #define nil NULL 
  82.  
  83. #ifdef __STDC__
  84. #define STRINGIZE(x) #x
  85. #else
  86. #define STRINGIZE(x) "x"
  87. #endif
  88.  
  89. #define name5(a,b,c,d,e)        name2(name2(a,b),name3(c,d,e))
  90.  
  91. #define declare1(a,t)           name2(a,declare1)(t)
  92. #define declare3(a,t1,t2,t3)    name2(a,declare3)(t1,t2,t3)
  93. #define declare4(a,t1,t2,t3,t4) name2(a,declare4)(t1,t2,t3,t4)
  94.  
  95. #define COMPARE(t,T) name3(t,T,_cmp) 
  96. #define APPLY(t,T)   name3(t,T,_apply) 
  97. #define ORD(t,T)     name3(t,T,_ord) 
  98.  
  99. #define Main            main(int argc, char** argv)
  100.  
  101. #define newline         (cout << "\n").flush()
  102.  
  103. #define forever         for(;;)
  104.  
  105. #define loop(a,b,c)     for (a=b;a<=c;a++)
  106.  
  107. #define Max(a,b)        ( (a>b) ? a : b )
  108.  
  109. #define Min(a,b)        ( (a>b) ? b : a )
  110.  
  111. #define SWAP(a,b)       if (a!=b) { *(int*)&a ^= int(b); \
  112.                     *(int*)&b ^= int(a); \
  113.                     *(int*)&a ^= int(b); }
  114.  
  115.  
  116. // iteration macros for lists and sets:
  117.  
  118. #define forall(x,S)       for((S).init_iterator(); (S).next_element(x); )
  119. #define forall_items(x,S) for(x = (S).first_item(); x; x = (S).next_item(x) )
  120.  
  121.  
  122. //------------------------------------------------------------------------------
  123. // compare, Print, Read, Init, Copy, Clear, Ent 
  124. // for basic builtin types
  125. //------------------------------------------------------------------------------
  126.  
  127. //overloaded compare: used to define linear orders in virtual cmp functions 
  128.  
  129. inline int compare(char& x, char& y)    { return x-y; }
  130. inline int compare(int&  x, int&  y)    { return x-y; }
  131. inline int compare(void* x, void* y)    { return int(x)-int(y); }
  132.  
  133. extern int compare(double&, double&);
  134.  
  135. //overloaded Print: used to define virtual print functions 
  136.  
  137. inline void Print(char& x, ostream& out = cout)  { out << x; }
  138. inline void Print(int&  x, ostream& out = cout)  { out << x; }
  139. inline void Print(void* x, ostream& out = cout)  { out << "0x" << hex(int(x)); }
  140.  
  141.  
  142. //overloaded Read: used to define virtual read functions 
  143.  
  144.  
  145. inline void Read(char& x, istream& in = cin)   { in >> x; }
  146. inline void Read(int&  x, istream& in = cin)   { in >> x; }
  147. inline void Read(void*, istream&)   {}
  148.  
  149.  
  150. //overloaded Init: used to define virtual initialization functions 
  151.  
  152. inline ent Init(char& x) { x=0; return ent(x); }
  153. inline ent Init(int&  x) { x=0; return ent(x); }
  154. inline ent Init(void* x) { x=0; return ent(x); }
  155.  
  156.  
  157. //overloaded Clear: used to define virtual clear functions
  158.  
  159. inline void Clear(char& x) { x=0; }
  160. inline void Clear(int&  x) { x=0; }
  161. inline void Clear(void* x) { x=x; }
  162.  
  163. //overloaded Copy: used to define virtual copy functions
  164.  
  165. inline ent Copy(const char& x)  { return ent(x); }
  166. inline ent Copy(const int&  x)  { return ent(x); }
  167. inline ent Copy(void* x)        { return ent(x); }
  168.  
  169.  
  170. //overloaded Ent:  used for converting pointer types to void* 
  171.  
  172. inline ent Ent(void* x) { return (void*)(x); }
  173. inline ent Ent(int   x) { return (void*)(x); }
  174.  
  175.  
  176. //------------------------------------------------------------------------------
  177. // Memory Management
  178. //------------------------------------------------------------------------------
  179.  
  180. struct  memory_elem_type { memory_elem_type* next; };
  181.  
  182. typedef memory_elem_type* memory_elem_ptr;
  183.  
  184.  
  185. extern const int memory_word_size;   // size of word   (in bytes) 4
  186. extern const int memory_block_bytes; // size of block  (in bytes) 2^k - 4
  187. extern const int memory_block_words; // size of block  (in words)
  188. extern const int memory_max_size;    // maximal size of a structure (words)
  189.  
  190. extern memory_elem_ptr memory_free_list[];
  191. extern long int        memory_total_count[];
  192.  
  193. extern memory_elem_ptr memory_block_list;
  194. extern int             memory_block_count;
  195.  
  196. extern void            memory_free_blocks();
  197. extern memory_elem_ptr memory_allocate_block(int);
  198. extern memory_elem_ptr allocate_words(int size);
  199. extern memory_elem_ptr Allocate_words(int size);
  200. extern void            deallocate_words(void* p, int size);
  201. extern void            Deallocate_words(void* p, int size);
  202. extern void            deallocate_list(void* head,void* tail, int size);
  203.  
  204. extern void            print_statistics();
  205.  
  206. inline memory_elem_ptr allocate_bytes(int n)
  207. { int s = n/memory_word_size;
  208.   if (n%memory_word_size) s++;
  209.   return allocate_words(s);
  210. }
  211.  
  212. inline void deallocate_bytes(void* p, int n)
  213. { int s = n/memory_word_size;
  214.   if (n%memory_word_size) s++;
  215.   deallocate_words(p,s);
  216. }
  217.  
  218.  
  219. #define OPERATOR_NEW(size)\
  220. void* operator new(size_t)\
  221. { memory_elem_ptr p = memory_free_list[size];\
  222.   if (p==0) p = memory_allocate_block(size);\
  223.   memory_free_list[size] = p->next;\
  224.   return p;\
  225.  }
  226.  
  227. #define OPERATOR_DEL(size)\
  228. void  operator delete(void* p)\
  229. { memory_elem_ptr(p)->next = memory_free_list[size];\
  230.   memory_free_list[size] = memory_elem_ptr(p);\
  231. }
  232.  
  233. //------------------------------------------------------------------------------
  234. // Basic Data Types
  235. //------------------------------------------------------------------------------
  236.  
  237. enum rel_pos { before = 1, after = 0 };
  238.  
  239. enum direction { forward = 0, backward = 1 };
  240.  
  241. //------------------------------------------------------------------------------
  242. // boolean
  243. //------------------------------------------------------------------------------
  244.  
  245.  
  246. /*
  247. enum bool { false = 0, true = 1 };
  248. */
  249.  
  250.  
  251. typedef int bool;
  252.  
  253. extern const bool true;
  254. extern const bool false;
  255.  
  256.  
  257.  
  258. //------------------------------------------------------------------------------
  259. // real numbers
  260. //------------------------------------------------------------------------------
  261.  
  262. class real{
  263.  
  264. struct rrep { 
  265.    
  266.       double d;     
  267.       int    n;     // number of references
  268.  
  269.  rrep(double x=0); 
  270.  
  271. OPERATOR_NEW(3)
  272. OPERATOR_DEL(3)
  273.  
  274. };
  275.  
  276. rrep* p;     
  277.  
  278. public:
  279.  
  280. real()               { p = new rrep; }
  281. real(const double d) { p = new rrep(d); }
  282. real(const int d)    { p = new rrep(d); }
  283. real(const real& r)  { p = r.p; p->n++; }
  284. real(ent x)          { p=(rrep*)x; p->n++; }
  285. void clear()         { if (--p->n == 0) delete p; }
  286.  
  287. ~real()              { clear(); }
  288.  
  289.  
  290. double operator~() const { return p->d; }
  291.  
  292. double* dp()       { return &(p->d); }
  293.  
  294. int round()        const { return (p->d>0) ? int(p->d+0.5) : int(p->d-0.5); }
  295. int trunc()        const { return int(p->d); }
  296.  
  297. operator double() const { return p->d; }  
  298.  
  299. real  operator-() const { return -(p->d); }
  300.  
  301. real& operator=(const double x);
  302. real& operator=(const real& x);
  303.  
  304. real& operator+=(const real& r)  { *this = p->d + r.p->d; return *this ; }
  305. real& operator+=(double d)       { *this = p->d + d;      return *this ; }
  306.  
  307. real& operator-=(const real& r)  { *this = p->d - r.p->d; return *this ; }
  308. real& operator-=(double d)       { *this = p->d - d;      return *this ; }
  309.  
  310. real& operator*=(const real& r)  { *this = p->d * r.p->d; return *this ; }
  311. real& operator*=(double d)       { *this = p->d * d;      return *this ; }
  312.  
  313. real& operator/=(const real& r)  { *this = p->d / r.p->d; return *this ; }
  314. real& operator/=(double d)       { *this = p->d / d;      return *this ; }
  315.  
  316.  
  317.  
  318.  
  319. friend ostream& operator<<(ostream&, const real&);
  320. friend istream& operator>>(istream&, real&); 
  321.  
  322. friend int  compare(real&, real&);
  323.  
  324. friend ent  Init(real& x)        { x.p->n++; return ent(x.p); }
  325. friend ent  Copy(const real& x)  { x.p->n++; return ent(x.p); }
  326. friend void Clear(real& x)       { x.clear(); }
  327. friend void Print(real& x, ostream& out = cout) { out << x; }
  328. friend void Read(real& x, istream& in = cin)    { in  >> x; }
  329.  
  330. friend ent  Ent(const real& x)    { return ent(x.p); }
  331.  
  332. };
  333.  
  334. //------------------------------------------------------------------------------
  335. // REAL(cmp): reals with user defined linear order cmp
  336. //------------------------------------------------------------------------------
  337.  
  338. #define REAL(cmp) name2(real_,cmp)
  339.  
  340. #define REALdeclare(cmp)\
  341. struct REAL(cmp) : public real \
  342. {  REAL(cmp)(ent p)        : real(p) {}\
  343.    REAL(cmp)(real  r )     : real(r) {}\
  344.    REAL(cmp)(REAL(cmp)& r) : real(r) {}\
  345.    REAL(cmp)() {}\
  346.   ~REAL(cmp)() {}\
  347. };\
  348. \
  349. int compare(REAL(cmp)& x, REAL(cmp)& y) { return cmp(x,y); }
  350.  
  351.  
  352. //------------------------------------------------------------------------------
  353. // INT(cmp): int with user defined linear order cmp
  354. //------------------------------------------------------------------------------
  355.  
  356. #define INT(cmp) name2(int_,cmp)
  357.  
  358. #define INTdeclare(cmp)\
  359. struct INT(cmp)\
  360. {  int p;\
  361.  INT(cmp)()                  { p = 0; }\
  362.  INT(cmp)(const int i)       { p = i;}\
  363.  INT(cmp)(ent x)             { p = (int)x; }\
  364.  operator int() { return p; }\
  365. \
  366. friend ent  Init(INT(cmp)&  x) { x.p = 0; return ent(x.p);}\
  367. friend ent  Copy(const INT(cmp)&  x) { return ent(x.p); }\
  368. friend void Clear(INT(cmp)& x) { x.p = 0; }\
  369. friend void Print(INT(cmp)& x, ostream& out = cout){ out << x.p; }\
  370. friend void Read(INT(cmp)&  x, istream& in = cin)  { in  >> x.p; }\
  371. friend ent  Ent(const INT(cmp)& x)                 { return ent(x.p); }\
  372. \
  373. };\
  374. \
  375. int compare(INT(cmp)& x, INT(cmp)& y) { return cmp(x,y); }
  376.  
  377.  
  378. //------------------------------------------------------------------------------
  379. // strings
  380. //------------------------------------------------------------------------------
  381.  
  382. extern char* str_dup(const char*);
  383. extern char* str_cat(const char*,const char*);
  384.  
  385. class string {
  386.  
  387. struct srep { 
  388.    
  389.       char* s;       // pointer to c-string
  390.       int   n;       // number of references
  391.  
  392. srep(char* p) { s = p; n = 1; }
  393.  
  394. OPERATOR_NEW(2)
  395. OPERATOR_DEL(2)
  396.  
  397. };
  398.  
  399.       srep* p;
  400.  
  401. public:
  402.  
  403.  
  404.   string()                { p = new srep(str_dup(""));}
  405.   string(const string& x) { x.p->n++; p = x.p; }
  406.   string(ent x)           { p=(srep*)x; p->n++; }
  407.   string(int  )           { p = new srep(str_dup("")); }
  408.  
  409.  string(const char*, ...);  // form-like constructor
  410.  
  411. #if defined(__GNUG__) || defined(__TURBOC__)
  412.  
  413. cfront: ambiguity  string(const char*, ...)  <--> string(const char*)
  414.  
  415. string(const char* s)   { PTR = new srep(s);}
  416.  
  417. #endif
  418.  
  419.  
  420.  void clear()       { if (--p->n == 0) { delete p->s; delete p; } }
  421.  
  422. ~string()           { clear(); }
  423.  
  424.  
  425. char*  operator~()  const   { return str_dup(p->s); }
  426. char*  cstring()    const   { return p->s; }
  427.  
  428. int    length()          const;
  429. string sub(int,int)      const;
  430. int    pos(string,int=0) const;
  431.  
  432. string operator()(int i, int j)  const { return sub(i,j); }
  433. string head(int i)               const { return sub(0,i-1); }
  434. string tail(int i)               const { return sub(length()-i,length()-1); }
  435.  
  436. string insert(string, int=0)             const;
  437. string insert(int, string)               const;
  438.  
  439. string replace(string, string, int=1)    const; 
  440. string replace(int, int, string)    const; 
  441.  
  442. string del(string, int=1)    const; 
  443. string del(int, int)         const; 
  444.  
  445. void   read(istream&, char=' ');
  446. void   read(char delim=' ')     { read(cin,delim); }
  447.  
  448. string replace_all(string s1, string s2) const  { return replace(s1,s2,0); } 
  449. string replace(int i, string s)          const  { return replace(i,i,s);  } 
  450.  
  451. string del_all(string s)                 const  { return del(s,0); }
  452. string del(int i)                        const  { return del(i,i); }  
  453.  
  454. void   read_line(istream& I = cin)              { read(I,'\n'); }
  455.  
  456. string format(string) const;
  457.  
  458. string& operator=(const char*);
  459. string& operator=(const string&);
  460.  
  461. char  operator[](int) const;
  462. char& operator[](int);
  463.  
  464. string operator+(const string& x)  const;
  465. string operator+(const char* s1)   const;
  466. string& operator+=(const char* s1);
  467. string& operator+=(const string& x);
  468.  
  469.  
  470. friend int operator==(const string& x, const char* s)   ;
  471. friend int operator==(const string& x, const string& y) ;
  472. friend int operator!=(const string& x, const char* s)   ;
  473. friend int operator!=(const string& x, const string& y) ;
  474. friend int operator<(const string& x, const string& y)  ;
  475. friend int operator>(const string& x, const string& y)  ;
  476. friend int operator<=(const string& x, const string& y) ;
  477. friend int operator>=(const string& x, const string& y) ;
  478.  
  479.  
  480. friend istream& operator>>(istream&, string&); 
  481. friend ostream& operator<<(ostream&, const string&) ;
  482.  
  483. friend int  compare(string& x, string& y);
  484.  
  485. friend ent  Init(string&  x)       { x.p->n++; return ent(x.p); }
  486. friend ent  Copy(const string&  x) { x.p->n++; return ent(x.p); }
  487. friend void Clear(string& x)       { x.clear(); }
  488. friend void Print(string& x, ostream& out = cout) { out << x; }
  489. friend void Read(string&  x, istream& in = cin)   { in  >> x; }
  490.  
  491. friend ent  Ent(const string& x)    { return ent(x.p); }
  492.  
  493. };
  494.  
  495. //------------------------------------------------------------------------------
  496. // STRING(cmp): string with user defined linear order cmp
  497. //------------------------------------------------------------------------------
  498.  
  499. #define STRING(cmp) name2(string_,cmp)
  500.  
  501. #define STRINGdeclare(cmp)\
  502. struct STRING(cmp) : public string \
  503. {  STRING(cmp)(ent p)          : string(p) {}\
  504.    STRING(cmp)(string s)       : string(s) {}\
  505.    STRING(cmp)(STRING(cmp)& s) : string(s) {}\
  506.    STRING(cmp)() {}\
  507.  ~ STRING(cmp)() {}\
  508. };\
  509. \
  510. int compare(STRING(cmp)& x, STRING(cmp)& y) { return cmp(x,y); }
  511.  
  512.  
  513. //------------------------------------------------------------------------------
  514. // some useful functions
  515. //------------------------------------------------------------------------------
  516.  
  517. typedef int (*SIG_PF) (...);
  518.  
  519. extern SIG_PF signal(int, SIG_PF);
  520.  
  521. extern int interrupt_handler(...);
  522.  
  523. inline SIG_PF catch_interrupts(SIG_PF handler = interrupt_handler)
  524. { return signal(2,handler); }
  525.  
  526.  
  527. #ifdef __TURBOC__
  528. inline void srandom(int seed) { srand(seed);   }
  529. inline int  random()          { return rand(); }
  530. #endif
  531.  
  532.  
  533. extern void    init_random(int=0);
  534. extern double  rrandom();                   // real random number in ]0..1[
  535.  
  536. inline unsigned random(unsigned a, unsigned b)  
  537.                   { return a + unsigned(random())%(b-a+1); }
  538.  
  539. inline int random(int a, int b)   { return a + random()%(b-a+1); }
  540.  
  541.  
  542.  
  543. extern double used_time();
  544. extern double used_time(real&);
  545. extern double used_time(double&);
  546. extern float  used_time(float&);
  547. extern void   print_time(string s);
  548.  
  549. inline void print_time() { print_time(""); }
  550.  
  551.  
  552.  
  553. //------------------------------------------------------------------------------
  554. // input/output
  555. //------------------------------------------------------------------------------
  556.  
  557. // Problems with cfront's stdarg on SPARCs
  558.  
  559. #define Va_Start  save_registers(); va_start
  560.  
  561. extern "C" void   save_registers(); // cfront&sparc: saves registers on stack
  562.                     // others: do nothing
  563.  
  564.  
  565. // if not GNU replace form calls by string constructor
  566.  
  567. #ifndef __GNUG__
  568. #define form ~string
  569. #endif
  570.  
  571.  
  572.  
  573. class file_ostream : public ostream {
  574.  
  575. filebuf fb;
  576.  
  577. public:
  578.  
  579. file_ostream() : ostream(&fb) {}
  580. file_ostream(string);
  581.  
  582. bool open(string);
  583. void close();
  584.  
  585. ~file_ostream() { close(); }
  586.  
  587. };
  588.  
  589.  
  590. class file_istream : public istream {
  591.  
  592. filebuf fb;
  593.  
  594. public:
  595.  
  596. file_istream() : istream(&fb) {}
  597. file_istream(string);
  598.  
  599. bool open(string);
  600. void close();
  601.  
  602. ~file_istream() { close(); }
  603.  
  604. };
  605.  
  606.  
  607.  
  608.  
  609. struct string_istream : public istream { 
  610.  
  611. char buf[2048];
  612.  
  613. public:
  614.  
  615. string_istream(string);
  616. string_istream(char*);
  617. string_istream(int, char**);
  618.  
  619. };
  620.  
  621.  
  622. class string_ostream : public ostream { 
  623.  
  624. char buf[2048];
  625.  
  626. public:
  627.  
  628. string_ostream();
  629. string str();
  630.  
  631. };
  632.  
  633.  
  634.  
  635. #ifndef __TURBOC__
  636.  
  637. struct cmd_ostream : public ostream {
  638.  
  639. #ifndef __GNUG__
  640.     stdiobuf b;
  641. #endif
  642. cmd_ostream(string);
  643.  
  644. };
  645.  
  646.  
  647. struct cmd_istream : public istream {
  648.  
  649. #ifndef __GNUG__
  650.     stdiobuf b;
  651. #endif
  652.  
  653. cmd_istream(string);
  654.  
  655. };
  656.  
  657. #endif
  658.  
  659.  
  660.  
  661.  
  662. extern int     Yes(string s);
  663. extern int     Yes();
  664.  
  665. extern int     read_int(string s);
  666. extern int     read_int();
  667.  
  668. extern char    read_char(string s);
  669. extern char    read_char();
  670.  
  671. extern double  read_real(string s);
  672. extern double  read_real();
  673.  
  674. extern string  read_string(string s);
  675. extern string  read_string();
  676.  
  677. extern string  read_line(istream& s);
  678. extern string  read_line();
  679.  
  680.  
  681. //------------------------------------------------------------------------------
  682. // Error Handling
  683. //------------------------------------------------------------------------------
  684.  
  685. typedef void (*PEH)(int,char*);   // Pointer to Error Handler
  686.  
  687. extern PEH p_error_handler;
  688. extern PEH set_error_handler(PEH);
  689. extern void default_error_handler(int,char*);
  690.  
  691.  
  692. inline void error_handler(int i, char* s)  { p_error_handler(i,s); }
  693. inline void error_handler(int i, string s) { p_error_handler(i,~s); }
  694.  
  695.  
  696. //------------------------------------------------------------------------------
  697. // LEDA INIT
  698. //------------------------------------------------------------------------------
  699.  
  700. extern const char* leda_version_string;
  701.  
  702. class LEDA_INIT {
  703.  
  704. char* init_list;
  705.  
  706. public:
  707.  
  708.  LEDA_INIT();
  709. ~LEDA_INIT();
  710.  
  711. };
  712.  
  713. extern LEDA_INIT LEDA;
  714.  
  715. #endif BASICH
  716.